// 给定整数数组nums和目标值target，
// 请设计算法在nums中找出任意三个数使得三数之和与target最接近，并返回三数和。
// 条件：已知每组输入只存在唯一答案。

var threeSumClosest: (nums: number[], target: number) => number = function (nums, target) {
    // 安全检测
    if (nums.length < 3) {
        return target;
    }
    // 初始化结果变量
    let res: number = nums[0] + nums[1] + nums[2];
    // 快速排序
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 2; i++) {
        // 左右指针初始化
        let left: number = i + 1;
        let right: number = nums.length - 1;
        // 三数之和-双指针算法，左右指针相等时结束循环
        while (left < right) {
            let sum: number = nums[i] + nums[left] + nums[right];
            // 如果当前三数和更接近目标值，则更新
            res = Math.abs(target - sum) < Math.abs(target - res) ? sum : res;
            // 左右指针根据情况依次滑动
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return sum;
            }
        }
    }
    return res;
};

        // 这道题也属于比较经典的一类模板题——求X数之和的类型
        // 如果之前没有做过的类似的题目话会比较难想
        // 解决这类问题的套路就是需要先对原数组进行排序得到有序数组
        // 然后用双指针算法来不断地维护结果变量
        // 具体做法是我们需要先对排序数组进行遍历
        // 在遍历的过程中，对当前元素i划分两个左右指针
        // 左指针下标为i+1，右指针则为数组末尾元素
        // 然后对左右指针与当前元素进行求和，判断当前三数和与结果变量哪个更接近target
        // 如果当前三数和更接近则更新结果变量
        // 之后我们判断三数和与目标值的大小关系，三数和小则左指针右移，三数和大则右指针左移，相等则直接返回
        // 我们通过双指针挪动不断与当前元素组合，直到左右指针相等时结束对当前元素的操作
        // 我们需要对除倒数1、2个元素之外的所有元素都进行一次上述的双指针算法
        // 当遍历结束时我们就能得到最接近的三数之和。